Проблема с набором вершин обратной связи, невозможность получить более низкий балл ⇐ JAVA

[Anonymous]

Я работаю над решением проблемы набора вершин с минимальной обратной связью (MinFVS) на двумерном геометрическом графе. Геометрический граф состоит из вершин, определяемых как точки на двумерной плоскости, с ребрами, существующими между двумя точками, если их евклидово расстояние меньше заданного порога.
Цель — найти минимальный набор вершин (FVS) для удаления так, чтобы оставшийся граф был ациклическим (лесом). Это для оцениваемого проекта, в котором производительность оценивается на основе среднего балла (размера FVS) за несколько запусков, стремясь к баллу ниже 83%.
Текущий алгоритм:
Предоставленный алгоритм состоит из следующих шагов:
Жадный подход: пытается итеративно удалить вершины с высокими степенями, пока оставшийся граф не станет ациклическим.
Локальный поиск: улучшает исходный жадное решение путем применения эвристики «удалить 2, добавить 1».
Итеративное улучшение: повторяет процесс три раза, чтобы найти лучшие решения.
Ключевые проблемы:
Решение часто застревает в локальных минимумах , что приводит к неоптимальным размерам FVS.
Шаги жадного и локального поиска алгоритма не эффективно исследуют пространство решений.
Чтобы добиться меньшего размера, необходимо повысить производительность FVS (оценка < 83%).
Код:
Ниже представлена ​​основная реализация.
` алгоритмов пакета;

Код: Выделить всё

import java.awt.Point;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;

public class DefaultTeam {

public ArrayList
 calculFVS(ArrayList points, int edgeThreshold) {
ArrayList result = (ArrayList)points.clone();

for (int i=0;i

Подробнее здесь: [url]https://stackoverflow.com/questions/79246114/feedback-vertex-set-problem-unability-to-get-a-lower-score[/url]