Перебор всех вариантов

Всем привет! Это моя первая проблема, с которой хотелось бы поделиться. Проблема сложная, но хотелось бы верить, что получится найти ее решение.

Я пытаюсь создать программу следующего типа: задается территория размером N*N (ее реализует отдельный класс), после этого в разных точках территории задается несколько летательных аппаратов (его также реализует отдельный класс), каждый из которых обозревает одинаковую площадь K*K. После этого программа должна просчитать оптимальный маршрут пути так, чтобы все эти аппараты за минимальное время "осмотрели" все клетки. За каждый шаг любой аппарат может сдвинуться вправо, влево, вверх или вниз, в зависимости от своего положения. Например, находясь в левом верхнем углу, он не сможет сдвинуться влево или вверх.

Идея реализации маршрута такая: предположим, есть 3 аппарата. В начальный момент времени у первого аппарата есть 3 возможных хода, у второго 2, у третьего 4. Метод, который ищет оптимальный путь, ищет один из возможных ходов, например, первый идет влево, второй вправо, третий вниз, после чего вызывает сам себя рекурсивно. Если посещены все клетки, то надо возвратить значение true и запомнить ходы, если на данный момент решение оптимально, и false иначе. Таким образом надо перебрать все возможные варианты. Да, это тупо, но после перебора всех вариантов точно известно, что конкретный вариант - лучший.

Проблема заключается в том, что изначально неизвестно, сколько всего аппаратов. Их может быть 2, а может быть 10 или даже 100. Соответственно, для 3 аппаратов, например, я бы написал 3 цикла for и перебрал бы все варианты. В идеале нужно сделать так - ход для первого, второго аппарата зафиксирован, для третьего рассматриваем возможные. Перешли на шаг вперед. Выяснили, что все клетки посещены, а решение неоптимально. Вернулись обратно, рассмотрели все шаги третьего аппарата - решение по-прежнему неоптимально. Взяли другой шаг второго аппарата - еще раз пересчитали все по третьему аппарату - неоптимально. Итого для начального момента времени из примера имеем 3*2*4 = 24 возможных хода. Получается, что надо рекурсивно рассмотреть все возможные ходы для одного момента времени, после чего опять-таки рекурсивно рассчитать, какой из них наилучший. А как реализовать это средствами C#?

Вложения

UAV.7z (42.9 Кб, 1 просмотров)

0

Маньяк,
Сначала рассмотрим вопрос теоретически. Число всевозможных путей аппаратов - огромно и растет экспоненциально. Поэтому рассмотреть абсолютно все варианты - невозможно. Следовательно вариант полного перебора отпадает. А значит точного решения нет. Это плохо.
С другой стороны есть хороший критерий оптимальности решения. Если каждый аппарат на каждом шагу будет покрывать новую точку (для упрощения примем что K = 1), то такое решение точно будет оптимально, потому что аппараты просмотрят максимально возможное число точек за одно и то же время и одновременно закончат просмотр. Это хорошо.

Далее. Учитывая критерий оптимальности, нужно распределить все множество точек между аппаратами так, что бы у каждого аппарата было одинаковое число точек. Помимо этого множества точек должны обладать свойством связности, что бы аппарат мог обследовать свое множество не пересекая другие множества. Ну и сам аппарат должен находится изначально в своем множестве точек.
Попутно заметим, что задача близка к диаграмме Вороного. Однако в диаграмме Вороного множества точек в общем случае имеют разную площадь, что нам не подходит. Однако, если изначально аппараты распределены более-менее равномерно на плоскости, то диаграмма Вороного даст неплохое приближение к оптимальному разбиению множества.

Далее. Алгоритмов разбиения можно предложить несколько. На вскидку:

1) Берем первый аппарат, присваиваем ему одну ближайшую незанятую точку. Далее берем второй аппарат, присваиваем ему тоже ближайшую незанятую точку. И так далее, пока все точки не закончатся. Понятно, что множество равномерно разобьется между аппаратами. В этом методе не гарантируется связность точек. Однако мне кажется он неплох.

2) Посчитаем центр масс всех точек и центр масс всех аппаратов. Проведем линию между этими двумя точками. Поскольку любая линия, проведенная через центр масс разбивает множество на две равные(!) части, то после разбиения у нас в каждой полуплоскости окажется одинаковое число аппаратов и одинаковое число точек. Далее для каждой полуплоскости снова считаем центр масс точек и центр масс аппаратов, и снова делим каждую полуплоскость на две равные части. И так далее, пока в каждом участке не окажется ровно один аппарат.

3) Итерационный метод. На каждом шагу аппарат движется к ближайшей незанятой точке, попутно отталкиваясь от общего центра масс аппаратов. Расталкивание гарантирует, что аппараты равномерно займут площадь поиска. Простой но не оптимальный алгоритм.

4) Модифицируем алгоритм диаграммы Вороного, так, что бы у каждого аппарата оказалось одинаковое число точек.
Ну и т.д.

Далее. Допустим мы разбили все множество точек между аппаратами. Как аппарату облетать эти точки? Тут несколько вариантов. Самое простое - летать вдоль границы. Тогда траектория будет похожа на спираль и не будет иметь самопересечений. Это хорошо сработает если множества точек не вытянутой формы.
Другой способ - двигать аппарат так, как в алгоритмах заливки. Однако движение вдоль границ кажется более предпочтительным вариантом.

0