[Homework] Greedy Algorithms

Здравейте,

предлагам да обсъдим задачите от това домашно тук. Като цяло, са доста по лесни от задачите от останалите домашни.

Аз обаче имам въпрос относно задачата Knight's Tour и той е ако имаме пътища с равна тежест, как избираме по кой от всичките да тръгнем?

Като цяло, моята програма изчислява пътя на коня, обаче output-а не съвпада с този от примера. Опитах се да нагаждам приоритета на различните ходове спрямо примерите, но когато го оправя за някои примери, останалите гърмят.

Код:

http://pastebin.com/aHD8EGtD

Зависи от реда на обхождане и от начина на взимане на най-малката стойност(прървата или последната срещната). Общо взето трябва да хвърляш боб, за да разбереш коя от всичките 8! = 40320 пермутации са използвани, за да се получи изхода от примерите. Аз като видях, че не става от всяка позиция нито по часовникоавата, нито в обратна посока се отказах. Реших, че някой е искал да се изгаври и е местил коня хаотично. Лесно може да се напише програма, която да проверява за всяка пермутация дали има съвпадение и за 3-те изхода едновременно, но според мен не си струва усилията.