http://Алик Кириллович/ ([identity profile] Алик Кириллович) wrote in [personal profile] shvarz 2011-06-07 10:49 pm (UTC)

Алгоритм: Смитта—Ватермана, а не Нидлмана—Вунша

>Эту игрушку прошли со всеми бонусами Нидлман с Вуншем еще в 70 году ;)

Скорее, все таки, не Нидлман с Вуншем (http://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algorithm) в 70 году, а Смитт с Ватерманом (http://en.wikipedia.org/wiki/Smith-Waterman_algorithm) в 80-м.

Дело в том, что в этой игре, судя по описанию, штраф за разрыв (http://en.wikipedia.org/wiki/Gap_penalty) является не линейный (как в алгоритме Нидлмана—Вунша), а афинным (как в алгоритме Смитта—Ватермана): т.е. за одну большую дырку снимается меньше баллов, чем за несколько маленьких.

Post a comment in response:

This account has disabled anonymous posting.
If you don't have an account you can create one now.
HTML doesn't work in the subject.
More info about formatting