Нахождение минимальных путей

Большое количество задач сводится к поиску минимальных путей между заданной парой вершин (или всеми парами вершин) в некотором графе (орграфе). Возможны различные варианты постановки задачи:

задача нахождения пути с минимальным количеством промежуточных вершин (как добраться из одного города в другой с наименьшим числом пересадок);

задача нахождения пути минимальной суммарной длины, если каждому ребру (дуге) приписано неотрицательное вещественное число (вес);

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

Размещение "центров", покрывающих заданную область.

Примеры задач данного типа:

размещение телевизионных или радиопередающих станций на некоторой территории;

размещение военных баз, контролирующих данную территорию;

размещение центров торговли, обслуживающих некоторый район.

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

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

Планирование производства.

Примеры задач данного типа: планирование производства на предприятиях пищевой, химической, фармацевтической и т.п. промышленности.

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

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