čtvrtek 19. listopadu 2015

Metric

A metric has has to fulfill following properties:
  1. Be symmetric
  2. Zero for d(A, A)
  3. Be non-negative
  4. Follow the triangle inequality
Symmetry is an useful property - the distance between city A and city B should be the same as the distance between city B and city A. However, if we were measuring gas consumption of a car and city B was on a hill and city A was in the valley bellow the hill, we would expect to see different results for a route from A to B (to the hill), than from a route from B to A (down the hill).

Similarly, zero property may not be always fulfilled - for example, a taxi fare is not a metric, because you pay a minimal fare just for sitting into the taxi.

Non-negativity is not be fulfilled whenever we are interested into the direction. For example, in transactions with money, we are commonly quite interested into the direction of the money transfer.

Triangle inequality is does not hold, for instance, what if we represent the weights between nodes as the time required to travel between the points  represented by the nodes.  Further, to make this scenario more physical, let us consider 3 points. A, B, and C.  Imagine that A and C
are separated by a lake, whereas a and b are on a bank such that I can walk from A to B on land, and on B to C on land.  Let's say I can walk the ABC path in about 15 minutes, but it will take me 30 minutes to swim across the lake from A to C.  This problem is a physical possibility, but it does not exhibit triangle inequality because I increase the cost of my path by removing an intermediary point.

Žádné komentáře:

Okomentovat