algorithmus gesucht für schnellste verbindungen



  • hi
    hab da ein problem.

    von einer reihe von orten (001-999) aus soll eine reihe anderer orte (AAA-ZZZ) erreicht werden, und zwar so, dass die längste verbindung so kurz wie möglich ist.
    Skizze: http://img165.imageshack.us/img165/9392/dstestdotyl7.jpg

    Nun hab ich gedacht, ich such für jeden start ort die kürzeste verbindung, und sortier sie nach der länge. die längste wird dann zuerst vergeben. mit den übrigen verbindungen wiederhol ich das dann solange, bis alle vergeben sind.

    bei diesem simplen beispiel oben funktioniert das ja, aber in einem testfall mit mehr knoten kommt auf diese weise nicht die beste lösung raus.
    ich grübel nun schon ne weile, obs ne andere möglichkeit gibt, ohne einfach zu raten und zu testen.

    hoffe jemand kann mir helfen 🙂





  • Ja, das könnte ein Ansatz sein. Wenn ich das Problem richtig verstehe, dann handelt es sich dabei um ein sogenanntes bottleneck matching problem. Also ein perfektes Matching, bei dem die längste Kante (der Bottleneck) möglichst kurz ist.

    Ich glaube ich hatte in diesem Buch mal was dazu gelesen. Dort war ein polynomieller Algorithmus angegeben.

    Combinatorial Optimization | ISBN: 9780486414539



  • ich hab das mal als "http://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden" kennengelernt...



  • Machine schrieb:

    ich hab das mal als "http://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden" kennengelernt...

    Das passt wohl nicht so ganz, weil beim Handlungsreisenden eine Rundreise über alle Orte gesucht wird und nicht kürzeste Verbindungen zwischen 2 Bipatiten Mengen.



  • start einfach nen contest dafuer 😉



  • also danke mal für die tipps. ungarische methode sieht gut aus, müsst ich mal ausprobiern.

    dann schreib ich mal nen preis aus:
    wer mir den schnellsten algorithmus liefert kriegt ein dankeschön 😃



  • jo manchmal nütz lesen was 😃
    hab in dem buch was über bipartite graphen und matching gelesen.
    Algorithmen in C++ | ISBN: 3893194622

    dann hab ich die stabilen ehen nach Knuth gebildet. das gibt bei meinem testfall eine gute lösung, bin aber nicht sicher ob er immer die beste lösung sucht.

    mach das nun so:
    -suche von jedem start die kürzeste verbindung zu einem ziel
    -suche die längste der kürzesten verbindungen und setzte deren länge als oberes limit
    -entferne alle verbindungen, die länger sind als das obere limit
    -versuche mit den restlichen verbindungen ein perfektes matching zu machen mithilfe des maximalen flusses im netzwerk
    --> existiert ein perfektes matching wurde eine ideale lösung gefunden, ansonsten wird das limit erhöt und nochmal probiert.

    wer was schnelleres weiss melden 😃



  • ja, das verfahren sollte funktionieren. im prinzip ist das auch eine art abgespecke ungarische Methode. Wenn du über eine Uni-Bib rankommst wirf doch mal einen Blick in das Buch von Lawler, soweit ich weiß war der Algorithmus dort recht ähnlich.

    Außerdem kannst Du vermutlich einiges an Zeit bei der Berechnung des Matchings sparen, wenn Du nicht jedesmal komplett von vorne rechnest (sieht man deine beschreibung nicht an, ob du das schon machst oder nicht). Falls nicht gewinnst Du damit wohl noch einen linearen Faktor...



  • ich wuerde alle moeglichen verbinden in ein array stecken, nach der groesse sortieren, jedem der 'orte' den count der 'anderen orte' geben. dann wuerde ich das sortierte array heruntergehen (vom groessten zum kleinsten) und bei den zwei orten einer verbindung jeweils den counter herunterzaehlen, gibt es mal einen counter der 0 wird, hat man die kuerzeste lange verbindung gefunden.

    hab jetzt aber nicht sonderlich lange nachgedacht ob es nen fall gibt bei dem das schief geht 😉



  • Den Algorithmus kapiere ich nicht. Ich verstehe nichtmal, was Du genau machen willst. Allerdings sieht es für das Problem ein bißchen zu einfach aus, ich fürchte ein bißchen mehr muß man schon investieren, ich denke nicht, dass sich das auf einfaches Sortieren zurückführen lässt.



  • Wirf doch mal den Code in die Menge.



  • *werf*

    import java.util.*;
    import data.*;
    
    public class AttackTimer {
    
    	// TODO: dooo...
    	private static int nextID = 0;
    
    	private class Attack {
    		public Attack(Coords s, Coords t) {
    			this.s = s;
    			this.t = t;
    			this.distSqr = s.distSqr(t);
    		}
    		public String toString() {
    			return this.s.toString() + " --> " + this.t.toString() + " " + this.distSqr;
    		}
    		public double distSqr;
    		public Coords s;
    		public Coords t;
    	}
    	private class ShortestAttackComparator
    							implements java.util.Comparator<Attack> {
    		public int compare(Attack a1, Attack a2) {
    			return (int)(a1.distSqr - a2.distSqr);
    		}
    	}
    
    	private class Coords {
    		public int id = -1;
    		public int x;
    		public int y;
    		public Coords(int x, int y) {
    			this.x = x;
    			this.y = y;
    			this.id = nextID++;
    		}
    		public double distSqr(Coords other) {
    			return Math.pow( Math.abs(this.x - other.x), 2)
    					+ Math.pow( Math.abs(this.y - other.y), 2);
    		}
    		public double dist(Coords other) {
    			return Math.sqrt(this.distSqr(other));
    		}
    		public String toString() {
    			return this.id + " " + this.x + "|" + this.y;
    		}
    	}
    	private class ShortestCoordsComparator
    							implements java.util.Comparator<Coords> {
    		private Coords t = null;
    		public ShortestCoordsComparator(Coords t) {
    			this.t = t;
    		}
    		public int compare(Coords s1, Coords s2) {
    			return (int)(t.distSqr(s1) - t.distSqr(s2));
    		}
    	}
    
    	private List<Coords> sources;
    	private List<Coords> targets;
    	private List<Attack> attacks;
    	private List<Attack> planA;
    	private List<Attack> planB;
    
    	private static final int WHITE = 0;
    	private static final int GRAY = 1;
    	private static final int BLACK = 2;
    
    	private int[][] cap;
    	private int[][] flow;
    	private int[] pred;
    	private int n;
    	private int e;
    	private int source;
    	private int sink;
    	private Attack[] attAr;
    
    	private void createNetwork() {
    		cap = new int[n][n];
    		for(int i = 0; i < n; ++i) {
    			for(int j = 0; j < n; ++j) {
    				cap[i][j] = 0;
    			}
    		}		
    		for( int i = 0; i < sources.size(); ++i ) {
    			cap[source][i] = 1;
    		}
    		for( int i = sources.size(); i < n-2; ++i ) {
    			cap[i][sink] = 1;
    		}
    	}
    	private void expandNetwork(int a) {
    		cap[attAr[a].s.id][attAr[a].t.id] = 1;
    	}
    	private boolean findAugmPath() {
    		int[] color = new int[n];
    		int[] queue = new int[n];
    		pred = new int[n];
    		for( int i = 0; i < n; ++i ) {
    			queue[i] = -1;
    			color[i] = WHITE;
    			pred[i] = -2;
    		}
    		int first = 0;
    		int last = 0;
    		queue[last++] = source;
    		color[source] = GRAY;
    		pred[source] = -1;
    		while( first != last ) {
    			int u = queue[first++];
    			color[u] = BLACK;
    			if( u == sink ) {
    				return true;
    			}
    			for( int v = 0; v < n; ++v ) {
    				if( color[v] == WHITE && cap[u][v]-flow[u][v] > 0 ) {
    					queue[last++] = v;
    					color[v] = GRAY;
    					pred[v] = u;
    				}
    			}
    		}
    		return false;
    	}
    	private int findMaxFlow() {
    		flow = new int[n][n];
    		for(int i = 0; i < n-2; ++i) {
    			for(int j = 0; j < n-2; ++j) {
    				flow[i][j] = 0;
    			}
    		}
    		int maxFlow = 0;
    		while( findAugmPath() == true ) {
    			for( int u = sink; pred[u] >= 0; u = pred[u] ) {
    				flow[pred[u]][u]++;
    				flow[u][pred[u]]--;
    			}
    			maxFlow++;
    		}
    		return maxFlow;
    	}
    
    	private void plan() {
    		planB = new ArrayList<Attack>();
    		n = targets.size()+sources.size()+2;
    		e = attacks.size();
    		source = n-2;
    		sink = n-1;
    		Collections.sort(attacks, new ShortestAttackComparator());
    		createNetwork();		
    		attAr = new Attack[e]; 
    		attAr = attacks.toArray(attAr);
    		int a = 0;
    		int maxFlow = 0;
    		while( a < e ) {
    			planB.clear();
    			int actualShortest = (int)attAr[a].distSqr;
    			while( a < e && (int)attAr[a].distSqr <= actualShortest ) {
    				expandNetwork(a);
    				a++;
    			}
    			int tmpFlow = findMaxFlow(); 
    			if( maxFlow < tmpFlow ) {
    				maxFlow = tmpFlow;
    				for( int i = 0; i < a; ++i ) {
    					if( 1 == flow[attAr[i].s.id][attAr[i].t.id] ) {
    						planB.add(attAr[i]);
    					}
    				}
    			}			
    			System.out.println( "For a distance of " + (int)attAr[a-1].distSqr + " attack " + tmpFlow + " from " + targets.size() + " villages" );
    			for( Attack aP : planB ) {
    				System.out.println( aP.toString() );
    			}
    		}		
    	}
    
    // nur zum testen
    	public AttackTimer() {
    
    		sources = new ArrayList<Coords>();
    		targets = new ArrayList<Coords>();
    		attacks = new ArrayList<Attack>();
    
    		sources.add( new Coords(0,0);
    		sources.add( new Coords(0,2);
    		sources.add( new Coords(2,0);
    		sources.add( new Coords(0,4);
    		sources.add( new Coords(4,0);
    		sources.add( new Coords(2,2);
    
    		targets.add( new Coords(0,6);
    		targets.add( new Coords(6,0);
    		targets.add( new Coords(8,8);
    		targets.add( new Coords(0,8);
    		targets.add( new Coords(8,0);
    		targets.add( new Coords(10,10);
    
    		for(Coords t : targets) {
    			for(Coords s : sources) {
    				attacks.add( this.new Attack( s, t ) );
    			}
    		}
    
    		plan();
    
    	}
    
    	public static void main(String[] args) {
    		new AttackTimer();		
    	}
    }
    


  • Ach, Du spielst in Wirklichkeit in der Ebene und die Gewichte sind die Punktabstände? -- Sag das doch gleich. 🙂

    Die Geometrie lässt sich ausnutzen, um zu einem schnelleren Algorithmus zu kommen.

    Alon Efrat, Alon Itai, Matthew J. Katz: Geometry Helps in Bottleneck Matching and Related Problems. Algorithmica 31(1): 1-28 (2001)

    Gibt einige Paper, die sich damit beschäftigen... "Improvements on bottleneck matching and related problems using geometry", "Solving the Euclidean Bottleneck Matching Problem by k-Relative Neighborhood Graphs" sind evtl. auch noch interessant. Ich schätze, dass du mindestens einen linearen Faktor noch durch nen Logarithmus ersetzen kannst im euklidischen Fall. Allerdings werden die Algorithmen dadurch nicht einfacher. 😉



  • cool, danke.

    werd mir die papers mal ansehn (ich mag papers, und ich mag komplizierte algos :D)
    und mich dann wieder melden.



  • ööhm, bei dem abschnitt über die datenstruktur kapier ich irgendwie gar nichts mehr:

    To simplify the notation, we scale the coordinates so that r = 1. Let S = {d1 , . . . , dn }
    be a set of unit disks, q ∈ R2 , and let the operation member(q, S) return a disk di ∈ S
    containing q, and ∅ if no such disk exists. In order to implement our algorithm, we need a
    data structure that supports efficiently membership queries and deletion of disks.
    To that end, we divide the plane using the axis-parallel grid Γ consisting of orthogonal
    cells of edge length 1/2 that passes through the origin. Since the disks have unit radius,
    each disk intersects O(1) cells, hence, only O(n) cells have a non-empty intersection with
    disks of S. We maintain these cells in a balanced search tree (ordered lexicographically).
    For each such cell Q, we maintain a list of disks whose center lies in Q, and a data structure
    Q
    Db , which maintains the upper envelope of Sb —the disks set of disks that intersect Q, and
    whose centers lie below the line containing the lower boundary of Q. (The upper envelope
    Q
    of Sb consists of all points p ∈ Q ∩ D∈S Q D such that no point of this union lies above p.)
    b
    Similar data structures Dl , Dr and Da are maintained for SlQ , Sr and Sa , the set of disks
    Q Q
    intersecting Q whose centers lie (respectively) to the left of, to the right of and above the
    lines containing the left, right and upper boundaries of Q. The space needed for Db will be
    Q
    shown to be O(|Sb |), and similarity for the other data structures. Since each disk intersects
    O(1) grid cells, the space requirement for all these data structures is O(n).
    To answer the query member(q, S), we consider the cell Q of Γ containing q in its interior
    (we ignore the degenerate and easy situation that q is on a boundary of a cell). If the center
    of a disk di lies inside Q then q ∈ di , and can be output as di = member(q, S). Otherwise,
    Q
    we use Db to find if any disk of Sb contains q, which happens if and only if q lies below the
    Q
    upper envelope of Sb . We repeat this process (if needed) for Dl , Dr and Da .
    Let us describe Db . The data structures Dl , Dr and Da are similar. Similar data structure
    was also used by Sharir [44]. Db is similar to the segment tree (Overmars and van Leeuwen
    Q
    [42]) and the one used by Hershberger and Suri [30]. Order the disks of Sb from left to
    right by their centers, and construct a complete binary tree T whose leaves are these disks.
    With each node v ∈ T we associate the set S(v) of disks corresponding to the leaves of the
    subtree rooted at v. Let UE(v) denote the upper envelope of S(v). As easily seen, not all
    the disks of S(v) must participate in UE(v), but those that do, appear along UE(v) (when
    scanned, from left to right) in the same order as the order of their centers, from left to right.

    Und zwar ist mir unklar, wie ich mir das mit dem 'envelope' vorstellen muss.


Log in to reply