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

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

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

  Yandex ТИЦ:  
   Google PR:  

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

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

Полные перебор, или поиск в ширину





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

Страница №6

Чтобы программа поиска маршрута выполняла поиск в ширину, необходимо изменить лишь подпрограмму isflight():

void isflight(char *from, char *to)
{
  int d, dist;
  char anywhere[20];

  while(dist=find(from, anywhere)) {
    /* модификация: поиск в ширину */
    if(d=match(anywhere, to)) {
      push(from, to, dist);
      push(anywhere, to, d);
      return;
    }
  }
  /* проверить любой авиарейс */
  if(dist=find(from, anywhere)) {
    push(from, to, dist);
    isflight(anywhere, to);
  }
  else if(tos>0) {
    pop(from, to, &dist);
    isflight(from, to);
  }
}

Как можно видеть, изменено только первое условие. Теперь проверяются все города, в которые можно попасть авиарейсом из пункта вылета, но из которых нет авиарейса в пункт прибытия.

Если этой версией isflight() заменить в программе предыдущую реализацию данной функции, то получится следующее решение:

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

Это решение является оптимальным. Путь к решению, найденный с помощью поиска в ширину, показан на рис. 25.6.

Рис. 25.6. Путь к решению, найденный с помощью поиска в ширину

Страница №7

Анализ поика в ширину

В этом примере поиск в ширину находит первое решение без возврата. Более того, оказывается, что это решение еще и оптимальное. В действительности первые три решения, которые могли бы быть найдены, как раз и являлись бы самыми лучшими маршрутами. Однако этот результат нельзя обобщить на другие случаи, потому что сгенерированный путь зависит от физической организации хранения информации в компьютере. Зато этот пример хорошо показывает радикальное отличие двух методов поиска: в глубину и в ширину.

Недостатки поиска в ширину становятся очевидными, когда цель находится на глубине нескольких слоев. В таком случае для поиска цели приходится затрачивать значительные усилия. В общем, выбирая один из двух методов поиска, в глубину или в ширину, Приходится делать обоснованные догадки о том, где вероятнее всего находится цель.


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

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.