Текущий архив: 2006.03.26;
Скачать: CL | DM;
Вниз
На доске (8х8) расставлено 8 ферзей Найти похожие ветки
← →
RiP (2006-02-21 12:34) [0]На доске (8х8) расставлено 8 ферзей (ферзь бьет по вертикали, горизонтали и диагонали). Убрать часть из них так, чтобы оставшиеся не били друг друга. Число оставшихся ферзей должно быть максимально.
хотя бы Подскажите кто нить алгоритм
← →
Ega23 © (2006-02-21 12:41) [1]Яндекс рулит.
А вообще - самостоятельно такие задачи надо решать. Их тебе в ВУЗе не просто так задают.
← →
TUser © (2006-02-21 14:51) [2]Строим граф G = (V, E), где V - это ферзи. (v1, v2) in E, тогда если ферзь v1 не бъет ферзя v2 и наоборот. Искомое множество ферзей - это максимальная клика в графе. В общем случае задача нерешаема (она NP-полная), но при таком размере я бы решил перебором.
См. также ссылки на тему "задача о вершинном покрытии".
Страницы: 1 вся ветка
Текущий архив: 2006.03.26;
Скачать: CL | DM;
Память: 0.47 MB
Время: 0.027 c
