Здравствуйте, vadimcher, Вы писали:
V>Здравствуйте, Элик, Вы писали:
Э>>Здравствуйте, vadimcher, Вы писали:
V>>>здесь
Э>>Часа три убил... Э>>
V> Бывает и больше... Главное не сдался! Добил ведь?
Кстати, у меня картника в конце другая получилась. Все 4 прямоугольника 1х2 наверху. Снизу 2х1 и 4 1х1 по два по бокам. Так что, видимо, есть разные варианты решить! Хотя даже один найти достаточно трудно.
Во, я получил в конце как раз такую расстановку, о чем я написал уже ранее. Неужели мне и вправду потребовалось пару сотен ходов (с учетом неоптимальности) !!! Решение для головоломки 4 на 5 в 116 ходов! Да, и вправду сурово...
Кстати, интересно посмотреть на путь в этой головоломке квадрата 2х2: в оптимальном решении его двигают первый раз только на 24-м ходу, до этого идет простая перетасовка мелких прямоугольников и квадратов, причем двигают его вбок, затем он остается там в углу еще на 46 ходов (!), и его сдвигают вниз, затем еще вниз через десяток ходов, а затем, когда до последней строчки остается все один шаг, его вместо этого прогоняют на другую сторону, к противоположной стенке, и только оттуда в нижний угол и к центру.
Это оказывается задача с контеста программирования в MIT.
Кто знает алгоритмы как такие задачи решать? Оказалось таких задач дофига и китайцы лет по 17-18 решают такие задачи как-то за вечер. Как они это делают?
Здравствуйте, PaulMinelly, Вы писали:
PM>Здравствуйте, vadimcher, Вы писали:
V>>здесь
PM>Это оказывается задача с контеста программирования в MIT. PM>Кто знает алгоритмы как такие задачи решать? Оказалось таких задач дофига и китайцы лет по 17-18 решают такие задачи как-то за вечер. Как они это делают?
Как китайцы -- не знаю. А написать алгоритм несложно: т.к. вариантов ходов достаточно мало и многие ветки приводят в тупик (когда приходится делать ход назад), то брутфорс тут самое оно.
PM>>Это оказывается задача с контеста программирования в MIT. PM>>Кто знает алгоритмы как такие задачи решать? Оказалось таких задач дофига и китайцы лет по 17-18 решают такие задачи как-то за вечер. Как они это делают?
V>Как китайцы -- не знаю. А написать алгоритм несложно: т.к. вариантов ходов достаточно мало и многие ветки приводят в тупик (когда приходится делать ход назад), то брутфорс тут самое оно.
Здравствуйте, PaulMinelly, Вы писали:
PM>Как написать такой алгоритм?
Ключевые слова: "рекурсия" или "дерево перебора"...
На С++, в данном случае, будет как-то так выглядеть:
bool find_solution( field_t& f, deque<move_t>& solution )
{
vector<move_t> candidates;
find_correct_moves( f, candidates );
for( vector<move_t>::size_type i = 0; i < candidates.size(); i++ ) {
const move_t& current = candidates[i];
field.do_move( current );
bool res = find_solution( field, solution );
field.undo_move( current );
if( !res )
continue;
solution.push_front( current );
return true;
}
return false;
}
deque<move_t> find_solutuon()
{
deque<move_t> result;
field_t start_position;
bool res = find_solution( start_position, result );
assert( res && start_position == field_t() );
return result;
}
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Здравствуйте, Erop, Вы писали:
E>Здравствуйте, PaulMinelly, Вы писали:
PM>>Как написать такой алгоритм? E>Ключевые слова: "рекурсия" или "дерево перебора"... E>На С++, в данном случае, будет как-то так выглядеть: [c]
Хотелось бы понять КАК строить такой алгоритм. Что считать ходом, откуда начинать, какой инвариант, что куда передвигать, какая сложность и т.п.?
Здравствуйте, PaulMinelly, Вы писали:
PM>Здравствуйте, Erop, Вы писали:
PM>Хотелось бы понять КАК строить такой алгоритм. Что считать ходом, откуда начинать, какой инвариант, что куда передвигать, какая сложность и т.п.?
А что не понятно? Ход -- перемещение одной фигуры на одну позицию.
Алгоритм очень простой -- полный перебор. Я же тебе сказал чего гуглить
Сложность -- объём дерева достижимых позиций.
На самом деле такой алгоритм, конечно, работать не будет, так как не гарантировно отсутсиве циклов. Но это тоже не сложно приделать, вообще-то. Типа в field_t хранить хыш на то, что уже в этой ветке встречалось, например...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
PM>>Хотелось бы понять КАК строить такой алгоритм. Что считать ходом, откуда начинать, какой инвариант, что куда передвигать, какая сложность и т.п.?
E>А что не понятно? Ход -- перемещение одной фигуры на одну позицию.
Как построить такое дерево, как закодировать позициии, по ним передвигать?
Догадываюсь надо будет выкинуть циклы из дерева (минимум O(n^2)), выбросить дубликаты-пути. Для этого надо хотя бы понять как все это должно быть представлено что есть интересная задача.
Сколько здесь возможных расстановок на доске?
E>Алгоритм очень простой -- полный перебор. Я же тебе сказал чего гуглить
Здравствуйте, PaulMinelly, Вы писали:
PM>Догадываюсь надо будет выкинуть циклы из дерева (минимум O(n^2)), выбросить дубликаты-пути. Для этого надо хотя бы понять как все это должно быть представлено что есть интересная задача.
Блин! Что тут сложного?
Ты не можешь придумать как задать какую-то конкретную позицию? Или не знаешь как по позиции сгенерить доступные ходы?
Если не можешь, то я не знаю как тебе помочь, а если можешь, то, типа осталось решить всего одну задачу -- научиться хранить множество уже посещённых позиций. Я бы использовал хэш-таблицу. Ну и всё. Ответ генератора фильтруем по уже посещённым позициям и вперёд...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
E>Ты не можешь придумать как задать какую-то конкретную позицию? Или не знаешь как по позиции сгенерить доступные ходы?
Да. Как задать конкретную позицию и как сгенерировать доступные ходы?
Здравствуйте, PaulMinelly, Вы писали:
E>>Ты не можешь придумать как задать какую-то конкретную позицию? Или не знаешь как по позиции сгенерить доступные ходы? PM>Да. Как задать конкретную позицию и как сгенерировать доступные ходы?
Ну придумай какой-нибудь представление...
Ты про эту конеретно гловоломку? Ну можешь иметь масиив NxM клеток, например, и в каждой клетке хранить номер фишки, которая её сейчас покрывает (либо 0, там, или -1, для пустой позиции).
Соответсвенно ход будет -- номер фигуры + направление смещения. А хэш сам как-нибудь родишь...
Но я думаю, что можно предложить и более эффективные представления. Сам теперь подумай немного, да?
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
Бывает и больше... Главное не сдался! Добил ведь?
!!! Решение для головоломки 4 на 5 в 116 ходов! Да, и вправду сурово...
! И саботировал работу половины конторы 
