>Эту игрушку прошли со всеми бонусами Нидлман с Вуншем еще в 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) является не линейный (как в алгоритме Нидлмана—Вунша), а афинным (как в алгоритме Смитта—Ватермана): т.е. за одну большую дырку снимается меньше баллов, чем за несколько маленьких.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
timeasmymeasure
Алгоритм: Смитта—Ватермана, а не Нидлмана—Вунша
Date: 2011-06-07 10:49 pm (UTC)Скорее, все таки, не Нидлман с Вуншем (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) является не линейный (как в алгоритме Нидлмана—Вунша), а афинным (как в алгоритме Смитта—Ватермана): т.е. за одну большую дырку снимается меньше баллов, чем за несколько маленьких.