Спонсоры сайта:

Наличие этой страницы в поиске?

Информеры ТИЦ и PR

  Yandex ТИЦ:  
   Google PR:  

Путешественникам, меломанам, бизнесменам, вебмастерам, новости.

Содержание | <<< | >>>

Поиск и использованием частичного пути минимальной стоимости





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

Если поиск с использованием частичного пути минимальной стоимости применять к задаче выбора маршрутов полетов, то это означает, что авиарейсы всегда выбираются самые короткие — в надеже, что и найденный маршрут окажется самым коротким. В отличие от наискорейшего подъема, который стремится уменьшить количество авиарейсов, поиск с использованием частичного пути минимальной стоимости сводит к минимуму общую длину маршрута.

Чтобы использовать поиск с использованием частичного пути минимальной стоимости, сначала, как обычно, нужно переписать функцию find(). Ниже показан ее новый код.

/* Найти самый близкий город и поместить его в "anywhere". */
int find(char *from, char *anywhere)
{
  int pos, dist;

  pos = 0;
  dist = 32000;  /* больше длины самого длинного авиарейса */
  find_pos = 0;

  while(find_pos < f_pos) {
    if(!strcmp(flight[find_pos].from, from) &&
      !flight[find_pos].skip) {
        if(flight[find_pos].distance<dist) {
        pos = find_pos;
        dist = flight[find_pos].distance;
      }
    }
    find_pos++;
  }
  if(pos) {
    strcpy(anywhere, flight[pos].to);
    flight[pos].skip = 1;
    return flight[pos].distance;
  }
  return 0;
}

С помощью этой версии find() получается такое решение:

Нью-Йорк - Торонто - Лос-Анджелес
Расстояние в милях равно 2600.

Как видите, в данном случае этот метод поиска позволяет найти самый короткий маршрут. Цепочка, ведущая к цели (т.е. маршрут, причем самый короткий), показана на рис. 25.8.

Рис. 25.8. Эта цепочка, ведущая к решению (т.е. путь, притом наикратчайший), была найдена методом поиска с использованием частичного пути минимальной стоимости

Страница №9

Анализ поиска с использованием частичного пути минимальной стоимости

Поиск с использованием частичного пути минимальной стоимости и наискорейший подъем имеют одни и те же достоинства и недостатки, но только с точностью до наоборот: то, что является достоинством одного метода, является недостатком другого, и наоборот. При поиске с использованием частичного пути минимальной стоимости могут появиться ложные, обманчивые "овраги, долины, низины и пропасти", но в целом этот метод работает достаточно хорошо. Однако не надо думать, что если поиск с использованием частичного пути минимальной стоимости работал в нашей задаче лучше, чем наискорейший подъем, то он вообще работает лучше[1]. Т.е. можно сказать, что в среднем он работает лучше, чем поиск вслепую.

----------

[1]Действительно, зная условие задачи, в которой поиск с использованием частичного пути минимальной стоимости работает лучше, можно сформулировать двойственную задачу, в которой будет лучше работать наискорейший подъем.


Содержание | <<< | >>>

C++ исходники. Все примеры - рабочие:

часы:

Dev C++ WinAPI Стрелочные часы Analog Clock

Dev C++ WinAPI Цифровые прозрачные часы. Текст на рабочем столе. Digital transparent clock. Text on desktop

Dev C++ OLE WinApi CALENDAR and DIGITAL CLOCK (15kb). Календарь и цифровые часы

Dev C++ OLE WinAPI Календарь и цифровые часы почти Vista SideBar всего 21kb

плееры:

Microsoft Visual C++ 2008 Direct Show DVD Mini Player 10.5kb

Dev C++ WinAPI Микро медиа плеер 3.5kb

Dev C++ WinAPI Мини медиа плеер 4.5kb

Dev C++ WinAPI Hint Всплывающая подсказка

Dev C++ WinAPI RECT - имитатор кнопки

Dev C++ WinAPI Заполнить ListBox

Dev C++ WinAPI Заполнить, редактировать, сохранить, загрузить ListBox (PlayList)

Dev C++ WinAPI Индикатор уровня

Dev C++ WinAPI MP3 Микро плеер Открыть с помощью...

Dev C++ WinAPI Своя кнопка

изображения:

Dev C++ GDI+ WinAPI Mini FotoResizer (16kb), изменяет размеры всех фото (JPG) до указанного размера в выбраной папке и её подпапках

Dev C++ WinAPI Сохранить BITMAP экрана, десктопа, окна, клиентской области.

Dev C++ WinAPI Изменить размер изображения BMP RESIZE. Загрузка изображений из ФАЙЛА, вывод на экран и сохранение в файл.

Dev C++ WinAPI Загрузка изображений из РЕСУРСОВ и вывод на экран.

Dev C++ GDI+ WinAPI. Преобразовать изображения из одного формата в другой (JPG в BMP, GIF, PNG и обратно ), используя дополнительные библиотеки GDI+. Загрузка изображений из файла и сохранение в файл.

Dev C++ GDI+ WinAPI масштабирование JPG RESIZE

Dev C++ OLE WinAPI. Преобразовать изображения из JPG в BMP, используя дополнительные библиотеки OLE. Загрузка изображений из РЕСУРСОВ и сохранение в файл.

Dev C++ OLE WinAPI преобразовать JPG в BMP, используя дополнительные библиотеки OLE. Загрузка изображений из ФАЙЛА и сохранение в файл.

Dev C++ OLE WinAPI масштабирование BMP RESIZE

разное:

Dev C++ WinAPI Dev C++ Преобразовать цвет точки экрана в HTML код

Dev C++ WinAPI NOTIFYICONDATA WS_EX_TOOLWINDOW Иконка в области уведомлений (notification area, tray, трей). Удалить с панели задач (taskbar).

Dev C++ WinAPI ShellExecute Создать ссылку на WEB сайт

Dev C++ WinAPI ShellExecute Создать окно со ссылкой на WEB сайт

Dev C++ WinAPI CreateProcess ShellExecute WinExec Запуск приложения из приложения

Dev C++ OLE WinAPI Создать регион Regions PopUp Меню Menu

Dev C++ FindFiles. Поиск файлов заданного типа (в примере *.JPG) в папке и её подпапках

библиотеки:

Скачать библиотеку GDI+ для Dev C++

Скачать справочнник с примерами языка C.