4430
правок
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) мНет описания правки |
||
(не показаны 3 промежуточные версии этого же участника) | |||
Строка 343: | Строка 343: | ||
Алгоритм FBB был внедрен в SIS/MISII [1] и протестирован на наборе больших тестовых схем ISCAS и MCNC на рабочей станции SPARC 10 с процессором с тактовой частотой 36 МГц и 32 МБ памяти. | Алгоритм FBB был внедрен в SIS/MISII [1] и протестирован на наборе больших тестовых схем ISCAS и MCNC на рабочей станции SPARC 10 с процессором с тактовой частотой 36 МГц и 32 МБ памяти. | ||
В таблице 1 приводится сравнение средних результатов алгоритма FBB в процессе биразбиения с результатами Дасдана и Эйканата из [3]. SN основан на применении эвристического алгоритма K&L в работе Санчиса [14]. PFM3 основан на применении эвристического алгоритма K&L со свободными перемещениями, как описано в [3]. На каждой схеме SN выполнялся 20 раз, а PFM3 – 10 раз с различными изначальными разбиениями, сгенерированными случайным образом. FBB | |||
В таблице 1 приводится сравнение средних результатов алгоритма FBB в процессе биразбиения с результатами Дасдана и Эйканата из [3]. SN основан на применении эвристического алгоритма K&L в работе Санчиса [14]. PFM3 основан на применении эвристического алгоритма K&L со свободными перемещениями, как описано в [3]. На каждой схеме SN выполнялся 20 раз, а PFM3 – 10 раз с различными изначальными разбиениями, сгенерированными случайным образом. FBB выполнялся 10 раз с различными случайным образом выбранными s и t. За единственным исключением FBB показал себя лучше SN и PFM3 на пяти схемах. В среднем FBB удалось найти биразбиение с количеством пересечений сеток на 24,5% и 19,0% меньше, чем SN и PFM3, соответственно. Время выполнения алгоритмов SN, PFM3 и FBB не сравнивалось, поскольку они выполнялись на разных рабочих станциях. | |||
== См. также == | == См. также == | ||
* [[Приближенное решение задачи о максимальном потоке]] | * [[Приближенное решение задачи о максимальном потоке]] | ||
* [[ | * [[Компоновка схемы]] | ||
* [[ | * [[Ресинхронизация схемы]] | ||
* [[Максимальный разрез]] | * [[Максимальный разрез]] | ||
* [[Минимальная бисекция]] | * [[Минимальная бисекция]] |
правок